package dp;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.List;

public class P473 {
    public boolean makesquare(int[] matchsticks) {
        int total = Arrays.stream(matchsticks).sum();
        if (total % 4 != 0) {
            return false;
        }
        //每条边的长度
        int edge = total / 4;
        return bt2(matchsticks, 0, new int[4], edge);
    }

    private boolean bt(int[] matchsticks, int begin, int target, List<Integer> savedList) {
        if (begin == matchsticks.length) {
            System.out.println(begin + "\t\t\t" + savedList);
            int count = 0;
            int totalLen = target;
            for (int idx : savedList) {
                if ((totalLen -= matchsticks[idx]) == 0) {
                    totalLen = target;
                    count++;
                }
            }
            return count == 4 ? true : false;
        } else {
            for (int i = 0; i < matchsticks.length; i++) {
                if (!savedList.contains(i)) {
                    savedList.add(i);
                    if (bt(matchsticks, begin + 1, target, savedList)) {
                        return true;
                    }
                    savedList.remove(savedList.size() - 1);

                }
            }
            return false;
        }
    }


    private boolean bt2(int[] matchsticks, int pos, int[] eachLength, int target) {
        if (pos == matchsticks.length) {
            int tmp = eachLength[0];
            for (int i = 0; i < eachLength.length; i++) {
                if (tmp != eachLength[i]) {
                    return false;
                }
            }
            return true;
        } else {
            int len = matchsticks[pos];
            for (int i = 0; i < eachLength.length; i++) {
                if (eachLength[i] + len <= target) {
                    eachLength[i] += len;
                    if (bt2(matchsticks, pos + 1, eachLength, target)) {
                        return true;
                    }
                    eachLength[i] -= len;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        boolean makesquare = new P473().makesquare(new int[]{5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3});
        System.out.println(makesquare);
    }
}
